class ArrayReader(object):
   def get(self, index):
       """
       :type index: int
       :rtype int
       """
       return 1

class Solution(object):
    def search(self, reader, target):
        """
        :type reader: ArrayReader
        :type target: int
        :rtype: int
        """
        left_index = 0
        right_index = 1
        value = reader.get(right_index)
        while value <= target:
            if value == target:
                return right_index
            left_index = right_index
            right_index = 2 * right_index
            value = reader.get(right_index)
        while right_index >= left_index:
            mid_index = (right_index + left_index) // 2
            value = reader.get(mid_index)
            if value == target:
                return mid_index
            else:
                if value < target:
                    left_index = mid_index + 1
                else:
                    right_index = mid_index - 1
        return -1
